The present invention relates to scheduling the processing of images in imaging devices, and in particular, to a method and an apparatus for providing an optimized schedule according to which a plurality of images are processed to maximize a productivity value.
"Imaging" or "marking," as used alternatively herein, is the entire process of putting an image (from a digital or an analog source) onto a medium, e.g., paper or another medium. In the case of a paper medium, the image can be permanently fixed to the paper by fusing, drying or other known methods. The present invention applies to any imaging device or system of devices in which the images are made electronically, including, e.g., electronic copiers and printers.
An imaging device typically includes a copy sheet paper path through which sheets or pages of the copy medium (e.g., plain paper) that are to receive an image are conveyed and imaged. The process of inserting copy sheets into the copy sheet paper path sequentially and controlling the movement of the copy sheets through the paper path to receive an image on one or both sides is referred to as "scheduling." A group of one or more desired images to be scheduled and printed is a "job."
The copy sheet paper path usually includes positions (i.e., pitches) for more than one copy sheet such that several sheets are sequentially processed at any given time. The copy sheets are printed as they circulate one or more times through the copy sheet paper path adjacent a marking station. Copy sheets that are printed on only one side (i.e., simplex copy sheets) in a single color usually pass through the copy sheet paper path once. Copy sheets that are printed on both sides (i.e., duplex sheets) usually pass through the copy sheet paper two or more times, although receiving images on both sides in a single pass is also possible. In addition to printing duplex images, multipass printing may be used to print color or highlighted images on one or both sides of the copy sheet. Conventional color printing, e.g., requires four passes through the transfer nip, i.e., one pass to transfer each of the four primary colors (black, magenta, yellow, and cyan). Accordingly, a scheduling routine must account for whether the output is desired in one of simplex, duplex or mixed formats, as well as whether the output is in color, in black and white or highlighted. Furthermore, because certain imaging operations require more processing time than others, e.g., duplex sheets may require more time to process than simplex sheets, an appropriate scheduler must also ensure that the sheets are output according to the desired sequence.
Other criteria also affect scheduling. For instance, a user may desire two or more sheets of the job to be stapled together or collated in a certain order. The user may desire to produce certain images on different sizes of copy stock. Certain images may need to be produced on orientation sensitive copy stock (e.g., paper having pre-punched holes along one of its edges). Each of these criteria, as well as others, imposes one or more constraints in scheduling the output of a job.
in addition, the construction and features, i.e., the architecture, of each imaging device imposes device-dependent constraints on scheduling. For example, the number of pitches of a photoreceptor and of a duplex loop portion of the paper path, the speed of the duplex loop and the conditions under which an imaging device resumes copying following a paper jam, each must be considered to provide a comprehensive scheduling routine. Consequently, providing a scheduling routine that accounts for all the criteria available to a user and satisfies both the image sequence and the device dependent (i.e., architectural) constraints is difficult.
As a result, each of the past efforts at scheduling focused on a specific type of imaging device, rather than the general class of imaging devices as a whole. Moreover, each conventional scheduling routine draws chiefly from empirical observations of various imaging sequences and procedures, rather than an analysis that primarily relies upon mathematical principles. Furthermore, the conventional scheduling routines, chiefly because of methodological differences and computation time limits, do not schedule each job directly based on the job in hand and a mathematical optimized minimum number of frames required to complete the job, but rather start each job based on experience and massage the tentative print schedule to yield an enhanced but imperfect result.
For example, U.S. Pat. Nos. 5,095,342 and 5,159,395 to Farrell et al. disclose methods of scheduling sheets in imaging devices having endless duplex paper path loops and dual mode duplex printing, respectively. U.S. Pat. No. 5,260,758 to Stemrole discloses a signature (i.e., an original typically having two or more pages per side) job copying system. U.S. Pat. No. 5,184,185 to Rasmussen discloses a method for scheduling duplex printing in which the gaps that occur between sheets of each set are selectively combined to minimize the number of required pitches. U.S. Pat. No. 5,130,750 to Rabb discloses cross-pitch scheduling of documents and copy sheets in an imaging device. U.S. Pat. No. 5,337,135 to Malachowski discloses a variable speed duplex drive for varying the rate at which sheets travel within the duplex loop so that the number of skipped pitches is reduced. Treating simplex sheets as simplex sheets under certain predetermined conditions to maximize the overall throughput of the imaging device is disclosed in an article by Covert in the Xerox Disclosure Journal, vol. 18, No. 4 (July/August 1993) at pp. 431-433. As illustrated by these examples, all of which are incorporated herein by reference, the conventional methods of scheduling jobs in an imaging device relate only to the specific constraints imposed by the architecture of that device.
Other constraint-based approaches to scheduling, such as forward scheduling and backward scheduling, have been suggested. These approaches differ from the present invention because they require preparing a tentative schedule of a first set based on constraint-based scheduling rules and then systematically constructing the remaining sets frame-by-frame either forwardly to get the second and third sets, etc., which is called the "forward method", or backwardly, taking the finished first set as the last set and construct the adjacent frames and sets in a backward manner up to the first set, which is called the "backward method." These approaches do not consider the whole print "job" in its entirety simultaneously in a mathematical optimization scheme. In other words, the present invention does not treat the first set, or any other set, with preference over the remaining sets. Rather, the scheduler according to the present invention treats all constraints equally, with few exceptions, and does not account for some architectural features first before accounting for others.
Moreover, the conventional methods of scheduling fail to address an important setting in which multiple imaging devices are used. In a modern print shop, for example, jobs are often divided into multiple tasks for processing in two or more imaging devices, each having particular capabilities and imposing certain constraints. The decision on how to divide the job into tasks, as well as the scheduling of each task, is carried out on an ad hoc basis. Therefore, in the case of an inexperienced user and/or a complicated job, the most efficient use of all the available imaging devices cannot be ensured.
One measure of the efficiency of an imaging device is its productivity. Productivity is defined as the actual number of pitches required in a job, in which a black-and-white simplex page is counted as one pitch, a full color page is counted as four, a duplex sheet is counted as having two pages, each page having one or four frames, divided by the actual number of required pitches necessary to complete the job. The actual number of required pitches usually exceeds the minimum number because of the skipped pitches necessary to conform to the constraints. In other words, to ensure that the images are output in the correct order, one or more skipped pitches may be scheduled following a previous image such that the previous image can be processed before the processing of a subsequent image is begun. As a result, productivity provides an efficiency measure by which the performance of imaging devices can be compared: an imaging device having a higher productivity for a particular job requires fewer pitches than an imaging device with a lower productivity. By maximizing the productivity of a particular imaging device, the processing time required to complete a job is minimized, and the throughput of the imaging device is maximized.